public class LinkedList {
     static class ListNode {
          public int val;
          public ListNode next;
          public ListNode prev;

          public ListNode(int val) {
               this.val = val;
          }
     }

     public ListNode head;
     public ListNode last;
     //头插法
     public void addFirst(int data){
          ListNode node = new ListNode(data);
          if(head == null) {
               head = node;
               last = node;
          }else {
               node.next = head;
               head.prev = node;
               head = node;
          }
     }
     //尾插法
     public void addLast(int data){
          ListNode node = new ListNode(data);
          if(head == null) {
               head = node;
               last = node;
          }else {
               last.next = node;
               node.prev = last;
               last = node;
          }
     }
     //任意位置插入,第一个数据节点为0号下标
     public boolean addIndex(int index,int data){
          int len = size();
          // 检查index是否合法
          if(index < 0 || index > len) {
               //可以抛出自定义的异常
               System.out.println("index位置不合法："+index);
               return false;
          }
          if(index == 0) {
               addFirst(data);
               return true;
          }
          if(index == len) {
               addLast(data);
               return true;
          }
          ListNode cur = findIndex(index);
          ListNode node = new ListNode(data);
          node.next = cur;
          cur.prev.next = node;
          node.prev = cur.prev;
          cur.prev = node;
     }
     //查找是否包含关键字key是否在双链表当中
     public boolean contains(int key){
          ListNode cur = head;
          while (cur != null) {
               if(cur.val == key) {
                    return true;
               }
               cur = cur.next;
          }
          return false;

     }
     //删除第一次出现关键字为key的节点
     public void remove(int key){
          ListNode cur = head;
          while (cur != null) {
               if(cur.val == key) {
                    if(cur == head) {
                         head = head.next;//head == null
                         if(head == null) {
                              last = null;
                         }else {
                              head.prev = null;
                         }
                    }else {
                         cur.prev.next = cur.next;
                         if(cur.next == null) {
                              last = last.prev;
                         }else {
                              cur.next.prev = cur.prev;
                         }
                   /* if(cur == last) {

                    }else {

                    }*/
                    }
                    return;
               }else {
                    cur = cur.next;
               }
          }
     }
     //删除所有值为key的节点
     public void removeAllKey(int key){
          ListNode cur = head;
          while (cur != null) {
               if(cur.val == key) {
                    if(cur == head) {
                         head = head.next;//head == null
                         if(head == null) {
                              last = null;
                         }else {
                              head.prev = null;
                         }
                    }else {
                         cur.prev.next = cur.next;
                         if(cur.next == null) {
                              last = last.prev;
                         }else {
                              cur.next.prev = cur.prev;
                         }
                    }
               }
               cur = cur.next;
          }
     }
     //得到双链表的长度
     public int size(){
          ListNode cur = head;
          int count = 0;
          while(cur != null){
               count++;
               cur = cur.next;
          }
          return count;
     }
     public void display(){
          ListNode cur = head;
          while (cur != null) {
               System.out.print(cur.val+" ");
               cur = cur.next;
          }
          System.out.println();
     }

     public void clear(){
          head = null;
          last = null;
     }
     private ListNode findIndex(int index) {
          ListNode cur = head;
          while (index != 0) {
               cur = cur.next;
               index--;
          }
          return cur;
     }
 }